package dse.modules.eln;

//import java.awt.Rectangle;
import java.util.Collection;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
//import java.util.SortedMap;
import java.util.TreeSet;
import java.util.Vector;

import testing.EarthLikeNetworkImagingUtil;
import testing.TestHelper;
import dse.Cluster;
import dse.DseException;
import dse.ExperimentConfiguration;
import dse.Network;
import dse.Node;
//import dse.Pair;
import dse.modules.ClusterGenerator;
import dse.modules.ModuleUtil;
import dse.IOUtil;

public class EarthLikeNetworkClusterGenerator implements ClusterGenerator {
	private int maxCluster;
	private int neighborhoodSize;
	//private double[][] distances;
	
	public void initalize (
			ExperimentConfiguration systemSettings, 
			Map<String, String> moduleSettings
			)
	throws DseException
	{
		ModuleUtil.SettingsReader sr = ModuleUtil.getSettingsReader(
				this.getClass(), moduleSettings
				);
		maxCluster = sr.getInteger("max-cluster");
		neighborhoodSize = sr.getInteger("neighborhood-size");
		//distances = null;
	}

	@SuppressWarnings({ "unchecked", "rawtypes"})
	public void generateClusters (Network network) {
		EarthLikeNetwork n = (EarthLikeNetwork)network;		

		//int w = n.getWidth();
		//int h = n.getHeight();
		/*distances = new double[n.nodeCount()][n.nodeCount()];
		for(int i=0; i<n.nodeCount(); i++)
			for(int j=0; j<n.nodeCount(); j++)
			{
				if(i < j)
				{
					NodeWithCoordinates x = (NodeWithCoordinates)n.lookupNode(i+1);
					NodeWithCoordinates y = (NodeWithCoordinates)n.lookupNode(j+1);
					
					distances[i][j] = GeometryUtil.distance(x.getX(), x.getY(), 
							y.getX(), y.getY());
				}
				else if(i==j)
					distances[i][j] = 0;
				else
					distances[i][j] = distances[j][i];
			}*/
		
		LinkedList<Cluster> clusters = new LinkedList<Cluster>();
		LinkedList<NodeWithCoordinates> nodes = 
			new LinkedList<NodeWithCoordinates>();
		nodes.addAll((Collection)network.nodes());
		
		//LinkedList<Pair<Integer,Rectangle>> clusterAreas = 
		//	new LinkedList<Pair<Integer,Rectangle>> ();
		
		generateClustersForArea(nodes,clusters);
		
		// Make sure all nodes are in a cluster!
		for (Node node : n.nodes())
			assert(node.clusterId() != Cluster.InvalidId);
		this.makeNeighborhoods(clusters);
		
		for(Cluster c : clusters)
		{
			n.addCluster(c);
		}
	}
	
	/*@SuppressWarnings("unchecked")
	Iterable<Pair<Integer,Rectangle>> generateClustersAndReturnData (
			Network network
			)
	{
		EarthLikeNetwork n = (EarthLikeNetwork)network;
		// Do our magci :D
		
		int w = n.getWidth();
		int h = n.getHeight();
		
		LinkedList<NodeWithCoordinates> nodes = 
			new LinkedList<NodeWithCoordinates>();
		nodes.addAll((Collection)network.nodes());
		
		LinkedList<Cluster> clusters = new LinkedList<Cluster>();
		LinkedList<Pair<Integer,Rectangle>> clusterAreas = 
			new LinkedList<Pair<Integer,Rectangle>> ();
		
		generateClustersForArea(
				0,0,w,h,nodes,clusters
				);
		
		
		
		// Make better super nodes
		chooseSuperNodes(n.clusters());
		
		return clusterAreas;
	}*/
	
	//@SuppressWarnings("unchecked")
	private void generateClustersForArea(LinkedList<NodeWithCoordinates> nodes,
			LinkedList<Cluster> clusters
			)
	{
		Vector<NodeWithCoordinates> seeds = new Vector<NodeWithCoordinates>(maxCluster);
		/*boolean isLessThanMaxSize = false;
		while(!isLessThanMaxSize)
		{
			Iterator<NodeWithCoordinates> itr = nodes.iterator();
			NodeWithCoordinates potential = nodes.getFirst();
			double minDistance = Double.MAX_VALUE;
			
			for(;itr.hasNext();)
			{
				isLessThanMaxSize = true;
				NodeWithCoordinates pt = itr.next();
				double distance = 0;
				facilities.add(pt);
				Iterator<NodeWithCoordinates> innerItr = nodes.iterator();
				for(;innerItr.hasNext();)
				{
					double dist = getNearestDistance(innerItr.next(), facilities);
					distance += dist;
					if(dist > maxDistance)
					{
						isLessThanMaxSize = false;
					}
				}
				facilities.remove(pt);
				if(minDistance > distance)
				{
					minDistance = distance;
					potential = pt;
				}
			}
			facilities.add(potential);
			nodes.remove(potential);
		}*/
		
		Hashtable<NodeWithCoordinates, Vector<NodeWithCoordinates>> cluster =
			new Hashtable<NodeWithCoordinates, Vector<NodeWithCoordinates>>();
		for(int i=0; i<maxCluster; i++)
		{
			seeds.add(nodes.get(i));
			cluster.put(nodes.get(i), new Vector<NodeWithCoordinates>());
		}
		
		do
		{
			Iterator<NodeWithCoordinates> itr = nodes.iterator();
			while(itr.hasNext())
			{
				NodeWithCoordinates pt = itr.next();
				cluster.get(this.getNearestNode(pt, seeds)).add(pt);
			}
		}while(refreshSeeds(seeds, cluster));
		
		//Iterator<NodeWithCoordinates> itr = nodes.iterator();
		/*Hashtable<Integer, Vector<Node>> ht = new Hashtable<Integer, Vector<Node>>();
		for(;itr.hasNext();)
		{
			NodeWithCoordinates node = itr.next();
			int clusterID = getNodeCluster(node, facilities);
			if(ht.get(clusterID) == null)
			{
				Vector<Node> v = new Vector<Node>();
				v.add(node);
				ht.put(clusterID, v);
			}
			else
			{
				ht.get(clusterID).add(node);
			}
		}*/	
		
		int i=0;
		for(NodeWithCoordinates seed : seeds)
		{
			EarthLikeNetworkCluster c = new EarthLikeNetworkCluster(i+1, seed.getX(), seed.getY());
			c.addNode(seed);
			//c.setSuperNode(seed);
			Vector<NodeWithCoordinates> vn = cluster.get(seed);
			for(NodeWithCoordinates node : vn)
			{
				if(node != seed)
					c.addNode(node);
			}
			
			clusters.add(c);
			i++;
		}
	}
	
	private NodeWithCoordinates getNearestNode(double x, double y, 
			Vector<NodeWithCoordinates> vNode)
	{
		double nearestDistance = Double.MAX_VALUE;
		NodeWithCoordinates result = null;
		for(int i=0; i<vNode.size(); i++)
		{
			NodeWithCoordinates iNode = vNode.get(i);
			double dist = GeometryUtil.distance(x, y, iNode.getX(), iNode.getY());
			if(nearestDistance > dist)
			{
				nearestDistance = dist;
				result = iNode;
			}
		}
		return result;
	}
	
	private NodeWithCoordinates getNearestNode(NodeWithCoordinates node, 
			Vector<NodeWithCoordinates> vNode)
	{
		double nearestDistance = Double.MAX_VALUE;
		NodeWithCoordinates result = null;
		for(int i=0; i<vNode.size(); i++)
		{
			NodeWithCoordinates iNode = vNode.get(i);
			double dist = GeometryUtil.distance(node.getX(), node.getY(), iNode.getX(), iNode.getY());
			if(nearestDistance > dist)
			{
				nearestDistance = dist;
				result = iNode;
			}
		}
		return result;
	}
	
	/*private int getNodeCluster(NodeWithCoordinates node, 
			Vector<NodeWithCoordinates> vNode)
	{
		double nearestDistance = Double.MAX_VALUE;
		int clusterID = -1;
		for(int i=0; i<vNode.size(); i++)
		{
			NodeWithCoordinates iNode = vNode.get(i);
			double dist = distances[node.id()-1][iNode.id()-1];
			//GeometryUtil.distance(node.getX(), node.getY(), iNode.getX(), iNode.getY());
			if(nearestDistance > dist)
			{
				nearestDistance = dist;
				clusterID = i+1;
			}
		}
		return clusterID;
	}*/

	private boolean refreshSeeds(Vector<NodeWithCoordinates> seeds, Hashtable<NodeWithCoordinates, Vector<NodeWithCoordinates>> cluster)
	{
		boolean result = false;
		for(NodeWithCoordinates seed : seeds)
		{
			Vector<NodeWithCoordinates> vn = cluster.get(seed);
			double x = 0;
			double y = 0;
			for(NodeWithCoordinates node : vn)
			{
				x += node.getX();
				y += node.getY();
			}
			x /= vn.size();
			y /= vn.size();
			
			NodeWithCoordinates newSeed = this.getNearestNode(x, y, vn);
			if(newSeed != seed)
			{	
				result = true;
				cluster.put(newSeed, vn);
				cluster.remove(seed);
			}
		}
		if(result)
		{
			for(Vector<NodeWithCoordinates> vn : cluster.values())
				vn.clear();
		}
		else
		{
			for(NodeWithCoordinates node : cluster.keySet())
			{
				if(cluster.get(node).size() < 10)
				{
					cluster.remove(node);
					result = true;
					break;
				}
			}
			if(result)
			{
				for(Vector<NodeWithCoordinates> vn : cluster.values())
					vn.clear();
			}
		}
		seeds.clear();
		seeds.addAll(cluster.keySet());
		return result;
	}
	/**
	 * This is used when generateClustersForArea encounters a case where there
	 * are more nodes at a single point in space than can fit into one cluster!
	 * 
	 * @param x
	 * @param y
	 * @param store
	 * @param nodes
	 * @param clusterAreas
	 */
	/*private void handleDegenerateCase (
			LinkedList<Cluster> clusters,
			)
	{
		while (nodes.isEmpty() == false) {
			Vector<NodeWithCoordinates> nodesForCluster = 
				new Vector<NodeWithCoordinates>(this.maxSize);
			while (nodesForCluster.size() < this.maxSize 
					&& nodes.isEmpty() == false
					)
			{
				nodesForCluster.add(nodes.removeFirst());
			}
			if (nodesForCluster.isEmpty())
				break;
			
			int cid = clusters.size() + 1;
			clusters.add(new EarthLikeNetworkCluster(
					cid, nodesForCluster, x, y
					));
			if (clusterAreas != null)
				clusterAreas.add(
						new Pair<Integer,Rectangle>(cid, new Rectangle(x,y,0,0))
						);
		}
	}
	
	private int half (int d) {
		return (int)(Math.ceil(d/2.0));
	}*/
	
	/**
	 * This is probably kinda slow, O(#clusters^2), might need to be sped up.
	 * 
	 * @param network
	 * @param clusterAreas
	 */
	private void makeNeighborhoods(LinkedList<Cluster> clusters)
	{
		Iterator<Cluster> itr = clusters.iterator();
		while(itr.hasNext())
		{
			EarthLikeNetworkCluster cluster = (EarthLikeNetworkCluster)itr.next();
			Vector<Cluster> cl = new Vector<Cluster>(clusters);
			cl.remove(cluster);
			Hashtable<Double, Cluster> ht = new Hashtable<Double, Cluster>();
			TreeSet<Double> sortedDistance = new TreeSet<Double>();
			
			for(int i=0; i<cl.size(); i++)
			{
				double distance = cluster.distanceTo(cl.get(i));
				while(ht.get(distance) != null)
					distance += 0.001;
				ht.put(distance, cl.get(i));
				sortedDistance.add(distance);
			}
			
			int i=0;
			Iterator<Double> ditr = sortedDistance.iterator();
			while(i<neighborhoodSize && ditr.hasNext())
			{
				double distance = ditr.next();
				cluster.addNeighboringCluster(ht.get(distance));
				i++;
			}
		}
	}

	/*private void fillInDistanceMapForMakingNeighborhoods (
			LinkedList<Pair<Integer, Rectangle>> clusterAreas, 
			int netWidth, int netHeight, 
			Vector<Cluster> cl, 
			Map<Cluster, Vector<Cluster>> nmap
			)
	{
		for (Pair<Integer, Rectangle> subject : clusterAreas) {
			SortedMap<Integer, Integer> clusterDists = 
				new TreeMap<Integer, Integer>();
			
			int cx = (int)(subject.second.getCenterX());
			int cy = (int)(subject.second.getCenterY());
			for (Pair<Integer, Rectangle> other : clusterAreas) {
				if (other.first.intValue() == subject.first.intValue())
					continue;
				
				int cx2 = (int)(other.second.getCenterX());
				int cy2 = (int)(other.second.getCenterY());
				
				int dist = (int)GeometryUtil.distance(
						cx, cy, cx2, cy2
						);
				
				// Make sure the dist is unique!
				while (clusterDists.get(dist) != null)
					dist++;
				clusterDists.put(dist, other.first);
			}
			
			// Take the first X as this clusters neighborhood
			Cluster me = cl.elementAt(subject.first-1);
			assert (subject.first.intValue() == me.id());
			
			int a = 0;
			nmap.put(me, new Vector<Cluster>(neighborhoodSize));
			for (Integer cid : clusterDists.values()) {
				Cluster they = cl.elementAt(cid-1);
				assert they.id() == cid.intValue();
				
				assert me.id() != they.id();
				
				boolean continueOuter = false;
				for (Cluster alreadyAdded : nmap.get(me))
					if (alreadyAdded.id() == they.id()) {
						continueOuter = true;
						break;
					}
				if (continueOuter)
					continue;
				
				nmap.get(me).add(they);
				a++;
				if (a >= neighborhoodSize)
					break;
			}
			
			int cs = nmap.get(me).size();
			assert cs == Math.min(neighborhoodSize, cl.size()-1);
			for (Cluster a2 : nmap.get(me)) {
				int dups = 0;
				for (Cluster b2 : nmap.get(me))
					if (a2.id() == b2.id()) dups++;
				assert dups == 1;
			}
			
		}
	}
	
	private void chooseSuperNodes (Iterable<Cluster> clusters) {
		// Simple but not good way:
		/*for (Cluster c : n.clusters()) {
			// Set better super node
			int maxId = c.maxLocalNodeId();
			Node node = c.lookupNode(maxId/2);
			c.setSuperNode(node);
		}*/
		
		// Good but very slow way
		/*for (Cluster c : clusters) {
			double minDist = 0;
			Node minDistNode = c.superNode();
			
			for (Node n : c.nodes()) 
				minDist += n.distanceTo(minDistNode);
			
			for (Node prospect : c.nodes()) {
				double dist = 0;
				for (Node test : c.nodes()) {
					dist += test.distanceTo(prospect);
				}
				
				if (dist < minDist) {
					minDist = dist;
					minDistNode = prospect;
				}
			}
			
			c.setSuperNode(minDistNode);
		}
	}*/	
	
	
	
	/**
	 * Test the cluster generator by creating an image!
	 * 
	 * @param args
	 * @throws Exception
	 */
	public static void main (String[] args) 
	throws Exception
	{
		if (args.length != 6 && args.length != 7) {
			System.out.println(
					"Usage: java -cp ... " +
					"dse.modules.eln.EarthLikeNetworkClusterGenerator " +
					"<nodes> <poles> <min-pull> " +
					"<max-distance> <neighborhood-size> <output-file> " +
					"(seed)"
					);
			System.exit(-1);
		}
		int nodeNum = Integer.parseInt(args[0]);
		
		EarthLikeNetworkClusterGenerator elncg = 
			new EarthLikeNetworkClusterGenerator ();
		
		ExperimentConfiguration ss = TestHelper.createSystemSettings(args, 6);
		
		EarthLikeNetwork network = TestHelper.createELNetwork(
				ss, args, 0, 1, 2
				);
		
		
		Hashtable<String, String> props = new Hashtable<String, String>();
		props.put("max-cluster", args[3]);
		props.put("neighborhood-size", args[4]);
		elncg.initalize(ss, props);
		
		
		System.out.println("Creating clusters...");
		long t1 = System.currentTimeMillis();
		System.out.println(t1);
		elncg.generateClusters(network);
		long t2 = System.currentTimeMillis();
		System.out.println(t2);
		System.out.println((t2-t1)/1000);
		/*GeneralNodeBandwidthAssigner gnba = new GeneralNodeBandwidthAssigner();
		Map<String, String> ms = new TreeMap<String, String>();
		ms.put("min", "100000");
		ms.put("max", "1000000");
		gnba.initalize(ss, ms);
		gnba.assignBandwidths(network);*/
		
		IOUtil.NetworkToFile(network, "network.dat");
		
		network = IOUtil.NetworkFromFile("network.dat");
		
		System.out.println(network.nodeCount()+" : " + network.nodes().size());
		
		/*Map<String, String> dms = new TreeMap<String, String>();
		dms.put("num-objects", "100");
		dms.put("min-size", "1000");
		dms.put("max-size", "10000000");
		dms.put("share-count", "10");
		dms.put("req-share-count", "5");
		
		GeneralDataObjectGenerator gdog = new GeneralDataObjectGenerator();
		gdog.initalize(ss, dms);
		Vector<DataObject> vd = gdog.generateDataObjects();
		
		IOUtil.DataObjectsToFile(vd, "dataobjects.dat");
		
		vd = IOUtil.DataObjectsFromFile("dataobjects.dat");
		
		GeneralDataObjectAccessRanker gdoar = new GeneralDataObjectAccessRanker();
		Map<String, String> arms = new TreeMap<String, String>();
		arms.put("diff", "30");
		gdoar.initalize(ss, arms);
		Map<Cluster, DataObjectAccessRanking> ar = gdoar.generateAccessRankings(network, vd);
		
		System.out.println("Before: " + ar.size());
		
		IOUtil.AccessRankingsToFile(ar, "accessrankings.dat");
		
		ar = IOUtil.AccessRankingsFromFile("accessrankings.dat");

		System.out.println("After: " + ar.size());
		
		for(Cluster c : ar.keySet())
		{
			System.out.println(c.id());
		}
		for(DataObjectAccessRanking d: ar.values())
		{
			System.out.println(d.toString());
		}
		*/
		// Validate it...
		int correctId = 1;
		for (Cluster c : network.clusters()) {
			assert c.id() == correctId;
			assert c == network.lookupCluster(c.id());
			
			assert c.neighborhoodSize() == elncg.neighborhoodSize;
			for (Cluster oc : c.neighborhood()) {
				assert oc == network.lookupCluster(oc.id());
				assert c != oc;
				assert c.id() != oc.id();
				
				int dups = 0;
				for (Cluster oc2 : c.neighborhood())
					if (oc.id() == oc2.id())
						dups++;
				assert dups == 1;
			}
			
			for (Node n : c.nodes())
				assert n.clusterId() == c.id();
			
			correctId++;
		}
		
		
		
		System.out.println("Creating image...");
		EarthLikeNetworkImagingUtil.saveImage(
				EarthLikeNetworkImagingUtil.drawClusters(
					EarthLikeNetworkImagingUtil.drawNetwork(network),
					network
					),
				args[5] // output filename
				);
		/*for (Cluster c : network.clusters()) {
			System.out.print("Cluster " + c.id() + " neighborhood: ");
			for (Cluster oc : c.neighborhood()) {
				System.out.print(" " + oc.id() + " ");
			}
			System.out.println();
		}*/
		
		System.out.println();
		
		int cc = network.clusterCount();
		System.out.println("Cluster count: " + cc);
		
		int countLessThan10 = 0;
		int countLessThan20 = 0;
		int countLessThan25PercentMax = 0;
		int countLessThan50PercentMax = 0;
		
		double avgSize = 0;
		for (Cluster c : network.clusters()) {
			//System.out.println("Cluster " + c.id() + " " + c.size());
			avgSize += c.size()/(double)cc;
			if (c.size() < 10)
				countLessThan10++;
			if (c.size() < 20)
				countLessThan20++;
			if (c.size() < nodeNum/10)
				countLessThan25PercentMax++;
			if (c.size() < nodeNum/4)
				countLessThan50PercentMax++;
		}
		System.out.println("Average size: " + avgSize);
		System.out.println(
				"Clusters w/ < 10 nodes: " + countLessThan10);
		System.out.println(
				"Clusters w/ < 20 nodes: " + countLessThan20);
		System.out.println(
				"Clusters w/ < MAX/4 nodes: " + countLessThan25PercentMax);
		System.out.println(
				"Clusters w/ < MAX/2 nodes: " + countLessThan50PercentMax);
		
		// Figure out super node to node distance...
		double dist = 0;
		for (Cluster c : network.clusters())
			for (Node n : c.nodes()) 
				dist += (n.distanceTo(c.superNode()))/network.nodeCount();
		System.out.println("Average node to super node distance: " + dist);
		
		System.out.println("Done.");
		
		/*for(Node node: network.nodes())
		{
			System.out.println("Node Id: " + node.id() + "; Cluster ID: " + node.clusterId());
		}*/
		
		for(Cluster c : network.clusters())
		{
			System.out.println("Cluster Id: " + c.id() + "; size: " + c.size());
			for(Node n : c.nodes())
			{
				System.out.println("Node " + n.localId() + " And " + n.id());
			}
		}
	}
}
